πŸ‘©β€πŸ’» 60062. μ™Έλ²½ 점검

@Seongukbaek Posted June 25, 2022 Β· Updated June 25, 2022 Β· 4 min read

문제

Programmers - μ™Έλ²½ 점검

πŸ“ Logic

private void canCheck(int[] friends) { for (int i = 0; i < weak.length; i++) { int start = i; boolean canCheck = true; for (int idx = 0; idx < friends.length; idx++) { for (int j = i; j < i + weak.length; j++) { // 두 지점 κ°„ 거리가 friends둜 λ½‘νžŒ μΉœκ΅¬κ°€ 점검 κ°€λŠ₯ν•œ 거리보닀 큰 κ²½μš°λŠ” 점검 λΆˆκ°€λŠ₯ // λ”°λΌμ„œ ν˜„μž¬ 지점을 μ‹œμž‘μ μœΌλ‘œ μ§€μ • if (unrolledWeak[j] - unrolledWeak[start] > friends[idx]) { start = j; idx++; // ν˜„μž¬ 지점을 점검할 수 μ—†λŠ”λ°, 더 점검할 μΉœκ΅¬κ°€ μ—†λ‹€λ©΄, μ’…λ£Œ if (idx == friends.length) { canCheck = false; break; } } } // 점검 μ™„λ£ŒλΌλ©΄, 더 이상 점검할 ν•„μš”κ°€ μ—†λ‹€. λ”°λΌμ„œ flagλ₯Ό true μ§€μ • if (canCheck) { answer = idx + 1; isFinish = true; return; } } } }
  • λ§Œλ“€μ–΄μ§„ 점검 인원을 μ΄μš©ν•΄ 점검이 κ°€λŠ₯ν•œμ§€ ν™•μΈν•œλ‹€.
  • μ·¨μ•½ 지점 κ°„ 거리λ₯Ό νƒμƒ‰ν•˜λ©΄μ„œ, λͺ¨λ‘ 점검이 κ°€λŠ₯ν•˜λ‹€λ©΄ answer λŠ” idx + 1 둜 μ—…λ°μ΄νŠΈλ˜κ³ , μ’…λ£Œλ₯Ό μœ„ν•΄ isFinish λ₯Ό μ—…λ°μ΄νŠΈν•΄ μˆœμ—΄ λ§Œλ“œλŠ” 것을 μ’…λ£Œν•œλ‹€.
  • 점검 인원을 λͺ¨λ‘ 동원해도 점검이 λΆˆκ°€λŠ₯ν•˜λ‹€λ©΄, 더이상 탐색을 μ’…λ£Œν•˜κ³ , λ‹€μŒ 점검 인원 μˆœμ—΄μ„ λ§Œλ“ λ‹€.

πŸ“„ CODE

μ½”λ“œ 보기/μ ‘κΈ°πŸ’«
class Solution { static int[] unrolledWeak; static boolean isFinish; static int[] weak; static int[] dist; static int answer = Integer.MAX_VALUE; public int solution(int n, int[] weak, int[] dist) { this.weak = weak; this.dist = dist; this.isFinish = false; int distLen = dist.length; unrollWeak(n, weak); // i개의 μˆœμ—΄ λ§Œλ“€κΈ° for (int i = 1; i <= distLen; i++) makeDistPerm(0, i, new boolean[distLen], new int[i]); return answer == Integer.MAX_VALUE ? -1 : answer; } private void makeDistPerm(int depth, int count, boolean[] visited, int[] friends) { if (isFinish) return; if (depth == count) { canCheck(friends); return; } for (int i = 0; i < dist.length; i++) { if (!visited[i]) { friends[depth] = dist[i]; visited[i] = true; makeDistPerm(depth + 1, count, visited, friends); visited[i] = false; } } } private void canCheck(int[] friends) { for (int i = 0; i < weak.length; i++) { int start = i; boolean canCheck = true; for (int idx = 0; idx < friends.length; idx++) { for (int j = i; j < i + weak.length; j++) { // 두 지점 κ°„ 거리가 friends둜 λ½‘νžŒ μΉœκ΅¬κ°€ 점검 κ°€λŠ₯ν•œ 거리보닀 큰 κ²½μš°λŠ” 점검 λΆˆκ°€λŠ₯ // λ”°λΌμ„œ ν˜„μž¬ 지점을 μ‹œμž‘μ μœΌλ‘œ μ§€μ • if (unrolledWeak[j] - unrolledWeak[start] > friends[idx]) { start = j; idx++; // ν˜„μž¬ 지점을 점검할 수 μ—†λŠ”λ°, 더 점검할 μΉœκ΅¬κ°€ μ—†λ‹€λ©΄, μ’…λ£Œ if (idx == friends.length) { canCheck = false; break; } } } // 점검 μ™„λ£ŒλΌλ©΄, 더 이상 점검할 ν•„μš”κ°€ μ—†λ‹€. λ”°λΌμ„œ flagλ₯Ό true μ§€μ • if (canCheck) { answer = idx + 1; isFinish = true; return; } } } } // weakλ₯Ό 1μ°¨μ›μœΌλ‘œ 펼침 private void unrollWeak(int n, int[] weak) { int len = weak.length; unrolledWeak = new int[len * 2 - 1]; System.arraycopy(weak, 0, unrolledWeak, 0, len); for (int i = 0; i < len - 1; i++) unrolledWeak[i + len] = weak[i] + n; } }

✏️ Review

  • μˆœμ—΄μ„ μ‚¬μš©ν•΄μ„œ 1, 2, ... nλͺ…μœΌλ‘œ κ°€λŠ₯ν•œμ§€ ν™•μΈν•΄λ³΄λŠ” 방식인 것은 μ‰½κ²Œ μ•Œμ•˜λ‹€!

    • ν•˜μ§€λ§Œ μ£Όμ–΄μ§„ μΈμ›μœΌλ‘œ μ™Έλ²½ 점검이 κ°€λŠ₯ν•œμ§€ ν™•μΈν•˜λŠ” 둜직 κ΅¬ν˜„μ—μ„œ μ’€ λ§‰ν˜”λ‹€...
  • κ΅¬ν˜„ μ—°μŠ΅μ„ 많이 ν•΄μ•Όκ² λ‹€.
@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€